package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/
 * @create 2025/11/2 15:37
 * @since JDK17
 */

public class Solution96 {
    int N = ((int) (1e9 + 7));
    public int numWays(int steps, int arrLen) {
        int max = Math.min(steps / 2, arrLen - 1);
        int[][] f = new int[steps + 1][max + 1];
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            for (int j = 0; j <= max; j++) {
                f[i][j] = f[i + 1][j];  // 不动
                if (j - 1 >= 0) {
                    f[i][j] = (f[i][j] + f[i + 1][j - 1]) % N;
                }
                if (j + 1 <= max) {
                    f[i][j] = (f[i][j] + f[i + 1][j + 1]) % N;
                }
            }
        }

        return f[0][0];
    }
}
